package com.yanceysong.codetop.s31_s40;


public class S31_Hard_72_编辑距离 {

    /**
     * 题目链接：
     * <a href="https://leetcode.cn/problems/edit-distance/">...</a>
     * <p>
     * 给定两个单词 word1 和 word2，计算将 word1 转换为 word2 所需的最少操作数。允许的三种原子操作：
     * 1. 插入一个字符 (Insert)
     * 2. 删除一个字符 (Delete)
     * 3. 替换一个字符 (Replace)
     * <p>
     * 经典动态规划（Dynamic Programming）问题 —— Levenshtein Distance。
     * <p>
     * =====================
     * 一、定义状态
     * =====================
     * dp[i][j] 表示：word1 的前 i 个字符 (word1[0..i-1]) 转换为 word2 的前 j 个字符 (word2[0..j-1]) 的最少编辑操作数。
     * <p>
     * =====================
     * 二、初始化（Base Case）
     * =====================
     * 1) dp[0][j]：空串 -> word2 前 j 个字符，需要 j 次插入
     * 2) dp[i][0]：word1 前 i 个字符 -> 空串，需要 i 次删除
     * <p>
     * =====================
     * 三、状态转移（Transition）
     * =====================
     * 设当前处理字符：c1 = word1[i-1], c2 = word2[j-1]
     * 1) 若 c1 == c2：无需额外操作
     * dp[i][j] = dp[i-1][j-1]
     * 2) 若 c1 != c2：三选一取最小，再 +1
     * a) 删除 c1：    dp[i-1][j]   + 1  (Delete)
     * b) 插入 c2：    dp[i][j-1]   + 1  (Insert)  // 相当于让 word1 先补齐 c2
     * c) 替换 c1->c2：dp[i-1][j-1] + 1  (Replace)
     * 所以：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
     * <p>
     * =====================
     * 四、答案
     * =====================
     * dp[len1][len2] 即为最终结果
     * <p>
     * =====================
     * 五、时间 / 空间复杂度
     * =====================
     * 时间：O(n * m)
     * 空间：O(n * m) （可用滚动数组优化为 O(min(n,m))，此处保留完整表格便于理解）
     * <p>
     * =====================
     * 六、图解示例（word1 = "horse", word2 = "ros"）
     * =====================
     * 索引说明：i 行代表 word1 前 i 个字符；j 列代表 word2 前 j 个字符；第 0 行/列代表空前缀。
     * <p>
     * 构建 DP 表（行：word1 前缀，列：word2 前缀）：
     * <p>
     * .       j→   0    1    2    3
     * .            Ø    r    o    s
     * .i  ┌───────────────────────────
     * .↓0 │  0    1    2    3
     * . 1 │  1    1    2    3       h
     * . 2 │  2    2    1    2       o
     * . 3 │  3    2    2    2       r
     * . 4 │  4    3    3    2       s
     * . 5 │  5    4    4    3       e
     * <p>
     * 解释若干关键格：
     * dp[1][1]：h vs r -> Replace => 1
     * dp[2][2]：ho vs ro -> o == o，继承 dp[1][1] = 1
     * dp[5][3]：horse -> ros 结果 = 3
     * 一条可行操作序列：horse -> rorse(替换h) -> rose(删除r) -> ros(删除e)
     * <p>
     * =====================
     * 七、与其它相似题的区别
     * =====================
     * 与「最长公共子序列」不同：编辑距离允许替换、插入、删除，衡量“变成一致”的最小修改次数；
     * 与「只允许插入删除」的距离不同：这里还可替换，因此可更短。
     * <p>
     * =====================
     * 八、可选优化
     * =====================
     * 仅需上一行与当前行可进行滚动数组优化，将空间降为 O(min(n,m))；
     * 若仅需要判断距离是否 <= K，可在转移中做剪枝。
     *
     * <p>建议：初学务必先写出完整二维 DP，结合表格理解三种操作的意义。</p>
     */
    public int minDistance(String word1, String word2) {
        // word1 与 word2 的长度（此处使用更语义化的名字，避免 n1/n2 不直观）
        int word1Length = word1.length();
        int word2Length = word2.length();

        // dp[row][col] 含义：word1 前 row 个字符 变成 word2 前 col 个字符 的最少操作数
        // 行对应 word1 的前缀长度，列对应 word2 的前缀长度
        int[][] dp = new int[word1Length + 1][word2Length + 1];

        // 初始化：第一行（word1 为空 -> 逐步插入构成 word2 前缀）
        for (int col = 1; col <= word2Length; col++) {
            dp[0][col] = col; // 空串变成 word2 前 col 个字符，需要 col 次插入
        }
        // 初始化：第一列（删光 word1 前缀变成空串）
        for (int row = 1; row <= word1Length; row++) {
            dp[row][0] = row; // word1 前 row 个字符 -> 空串，需要 row 次删除
        }

        // 填表：自顶向下，自左向右
        for (int row = 1; row <= word1Length; row++) {
            char c1 = word1.charAt(row - 1); // 当前考虑的 word1 末尾字符
            for (int col = 1; col <= word2Length; col++) {
                char c2 = word2.charAt(col - 1); // 当前考虑的 word2 末尾字符

                if (c1 == c2) {
                    // 字符相同：无需额外操作，直接继承左上角（保持末尾字符）
                    dp[row][col] = dp[row - 1][col - 1];
                } else {
                    // 三种可能：
                    // 1) 删除：删除 word1 的 c1 -> 看 (row-1, col)
                    int deleteCost = dp[row - 1][col] + 1; // 删除 c1 这一步 +1
                    // 2) 插入：在 word1 末尾插入 c2，使其和 word2[col-1] 对齐 -> 看 (row, col-1)
                    int insertCost = dp[row][col - 1] + 1; // 插入 c2 这一步 +1
                    // 3) 替换：把 c1 替换成 c2 -> 看 (row-1, col-1)
                    int replaceCost = dp[row - 1][col - 1] + 1; // 替换操作 +1

                    // 取最小（最优策略）
                    dp[row][col] = Math.min(deleteCost, Math.min(insertCost, replaceCost));
                }
            }
        }

        // 最终答案：完整 word1 -> 完整 word2
        return dp[word1Length][word2Length];
    }

    public static void main(String[] args) {
        S31_Hard_72_编辑距离 solution = new S31_Hard_72_编辑距离();
        System.out.println("=== 编辑距离测试开始 ===");

        System.out.println("\n--- 测试1: 题目示例1 horse -> ros ---");
        testExample1(solution);

        System.out.println("\n--- 测试2: 题目示例2 intention -> execution ---");
        testExample2(solution);

        System.out.println("\n--- 测试3: 空串与空串 ---");
        testEmptyBoth(solution);

        System.out.println("\n--- 测试4: 其中一个为空 ---");
        testOneEmpty(solution);

        System.out.println("\n--- 测试5: 相同字符串 ---");
        testIdentical(solution);

        System.out.println("\n--- 测试6: 单字符差异 ---");
        testSingleChar(solution);

        System.out.println("\n--- 测试7: 完全不同(同长度) ---");
        testCompletelyDifferent(solution);

        System.out.println("\n--- 测试8: 部分重叠 kitten -> sitting ---");
        testKittenSitting(solution);

        System.out.println("\n--- 测试9: 较大规模(性能/边界趋势) ---");
        testLargerCase(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    private static void testExample1(S31_Hard_72_编辑距离 s) {
        String w1 = "horse";
        String w2 = "ros";
        int ans = s.minDistance(w1, w2);
        System.out.println("输入: horse -> ros, 输出: " + ans + " (期望: 3)");
        assert ans == 3 : "horse -> ros 应为 3";
    }

    private static void testExample2(S31_Hard_72_编辑距离 s) {
        String w1 = "intention";
        String w2 = "execution";
        int ans = s.minDistance(w1, w2);
        System.out.println("输入: intention -> execution, 输出: " + ans + " (期望: 5)");
        assert ans == 5 : "intention -> execution 应为 5";
    }

    private static void testEmptyBoth(S31_Hard_72_编辑距离 s) {
        String w1 = "";
        String w2 = "";
        int ans = s.minDistance(w1, w2);
        System.out.println("输入: 空 -> 空, 输出: " + ans + " (期望: 0)");
        assert ans == 0 : "空串对空串应为 0";
    }

    private static void testOneEmpty(S31_Hard_72_编辑距离 s) {
        String w1 = "";
        String w2 = "abc";
        int ans1 = s.minDistance(w1, w2);
        System.out.println("输入: 空 -> abc, 输出: " + ans1 + " (期望: 3)");
        assert ans1 == 3 : "空 -> abc 应为 3";

        String w3 = "abcd";
        String w4 = "";
        int ans2 = s.minDistance(w3, w4);
        System.out.println("输入: abcd -> 空, 输出: " + ans2 + " (期望: 4)");
        assert ans2 == 4 : "abcd -> 空 应为 4";
    }

    private static void testIdentical(S31_Hard_72_编辑距离 s) {
        String w1 = "algorithm";
        String w2 = "algorithm";
        int ans = s.minDistance(w1, w2);
        System.out.println("输入: algorithm -> algorithm, 输出: " + ans + " (期望: 0)");
        assert ans == 0 : "相同字符串应为 0";
    }

    private static void testSingleChar(S31_Hard_72_编辑距离 s) {
        String w1 = "a";
        String w2 = "b";
        int ans = s.minDistance(w1, w2);
        System.out.println("输入: a -> b, 输出: " + ans + " (期望: 1)");
        assert ans == 1 : "a -> b 应为 1 (替换)";

        String w3 = "a";
        String w4 = "aa";
        int ans2 = s.minDistance(w3, w4);
        System.out.println("输入: a -> aa, 输出: " + ans2 + " (期望: 1)");
        assert ans2 == 1 : "a -> aa 应为 1 (插入)";
    }

    private static void testCompletelyDifferent(S31_Hard_72_编辑距离 s) {
        String w1 = "abcd";
        String w2 = "wxyz"; // 可直接全部替换 => 4
        int ans = s.minDistance(w1, w2);
        System.out.println("输入: abcd -> wxyz, 输出: " + ans + " (期望: 4)");
        assert ans == 4 : "abcd -> wxyz 应为 4";
    }

    private static void testKittenSitting(S31_Hard_72_编辑距离 s) {
        String w1 = "kitten";
        String w2 = "sitting"; // 经典示例 => 3
        int ans = s.minDistance(w1, w2);
        System.out.println("输入: kitten -> sitting, 输出: " + ans + " (期望: 3)");
        assert ans == 3 : "kitten -> sitting 应为 3";
    }

    private static void testLargerCase(S31_Hard_72_编辑距离 s) {
        // 构造两个长度 30 的字符串，其中一半相同，一半不同
        StringBuilder a = new StringBuilder();
        StringBuilder b = new StringBuilder();
        for (int i = 0; i < 15; i++) {
            a.append('a');
            b.append('a');
        }
        for (int i = 0; i < 15; i++) {
            a.append('b');
            b.append('c');
        }
        String w1 = a.toString();
        String w2 = b.toString();
        // 前 15 个相同 (a vs a)，后 15 个全部需要替换 (b -> c) => 15
        int ans = s.minDistance(w1, w2);
        System.out.println("输入: 30长度(前15相同后15不同)，输出: " + ans + " (期望: 15)");
        assert ans == 15 : "应为 15 (后半段逐个替换)";
    }
}
